#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

// 物品结构体类型
struct Goods	
{
	// 物品的编号
	int no;
	
	// 物品的重量
	int w;
	
	// 物品的价值
	int v;
	
	// 构造函数
	Goods(int no1, int w1, int v1)
	{
		no=no1;
		w=w1;
		v=v1;
	}
	
	// 用于按v/w递减排序 -- 比较单位价值
	bool operator<(const Goods&s) const
	{
		return (double)v/w > (double)s.v/s.w;
	}
};

// 4种物品
int n=4;	

// 背包容量
int W=3;	

// 4种物品
vector<Goods> g = {Goods(0,3,9), Goods(1,1,2), Goods(2,2,8), Goods(3,2,6)};

// 存放最优解向量
vector<int> bestx;

// 存放最大价值,初始为0
int bestv = 0;

// 输出最优解
void disp()
{
	printf("最佳装填方案\n");
	for (int i=0;i<n;i++)
		if (bestx[i]==1)
			printf("  选取第%d个物品\n",g[i].no);
	printf("  总重量=%d,总价值=%d\n",W,bestv);
}

// 计算第i层结点的上界函数值
double bound(int cw,int cv,int i)
{
	// 背包的剩余容量
	int rw=W-cw;
	
	// 表示物品价值的上界值 
	double b=cv;
	int j=i+1;
	while (j<n && g[j].w<=rw)
	{
		// 选择物品j
		rw -= g[j].w;
		
		// 累计价值
		b += g[j].v;
		j++;
	}
	
	// 最后物品只能部分装入
	if (j < n)
		b += (double)g[j].v/g[j].w*rw;
	return b;
}

// 累计搜索的结点个数
int sum = 0;

// 回溯算法
void dfs(int cw, int cv, vector<int>&x, int i) 
{
	sum++;
	printf("[%d,%d]\n", cw, cv);
	
	// 找到一个叶子结点
	if (i >= n)
	{
		printf("找到一个解[%d,%d]\n", cw, cv);
		
		// 找到一个满足条件的更优解,保存它
		if (cw<=W && cv>bestv)
		{
			bestv = cv;
			bestx = x;
		}
	}
	
	// 没有到达叶子结点
	else
	{
		// 左剪支
		if(cw+g[i].w <= W)
		{
			// 选取物品i
			x[i]=1;
			dfs(cw+g[i].w, cv+g[i].v, x, i+1);
		}
		else
			printf("左剪支[%d,%d]\n",cw+g[i].w,cv+g[i].v);
		
		// 右剪支
		double b = bound(cw, cv, i);
		if(b > bestv)
		{
			printf("扩展右孩子结点b=%g\n", b);
			x[i]=0;								// 不选取物品i 
			dfs(cw,cv,x,i+1);
		}
		else
			printf("右剪支[%d,%d],b=%g\n",cw,cv,b);
	}
}

// 输出物品信息：编号、重量、价值、单位价值
void dispg()
{
	for(int i=0;i<g.size();i++)
		printf("%d\t%d\t%d\t%g\n", g[i].no, g[i].w, g[i].v, (double)g[i].v/g[i].w);
}

// 求解0/1背包问题
void knap()
{
	// 存储解向量
	bestx.resize(n);
	vector<int> x(n);
	
	// 物品按单位价值排序
	sort(g.begin(), g.end());
	
	// 输出物品信息
	printf("sort\n"); dispg();
	
	// i从0开始
	dfs(0, 0, x, 0);
	
	// 输出问题的解
	disp();
}

int main()
{
	// 输出物品信息
	printf("g:\n"); dispg();
	
	// 求解0/1背包问题
	knap();
	
	// 最大装载价值
	printf("sum=%d\n", sum);
	return 0;
}
